/// 子数组问题


use std::fmt::{Display, Formatter, Pointer};
use std::iter::zip;

/// https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked
/// 560. 和为 K 的子数组
/// 给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。
/// TIP: 对于连续且存在递推关系的数据，优先考虑前缀和
// pre[x]代表前x个数据的和 pre[j−1] == pre[i]−k就是地推公式
// 由于递推获取前缀和是O1，所以可以很方便的用hash统计（value,count）
pub fn subarray_sum(nums: Vec<i32>, k: i32) -> i32 {
    let mut record = std::collections::HashMap::new();
    // 优先创建初始值
    record.insert(0, 1);
    let mut cnt = 0;
    let mut total = 0;
    for x in nums {
        total += x;
        if record.contains_key(&(total - k)) {
            cnt += record[&(total - k)];
        }
        record.entry(total)
            .and_modify(|e| *e += 1)
            .or_insert(1);
    }
    cnt
}

pub fn subarray_sum2(nums: Vec<i32>, k: i32) -> i32 {
    let mut cache = std::collections::HashMap::from([(0, 1)]);
    let (mut pre, mut result) = (0, 0);
    for val in nums {
        pre += val;
        if let Some(&t) = cache.get(&(pre - k)) {
            result += t;
        }

        *cache.entry(pre).or_insert(0) += 1;
    }

    result
}

#[test]
pub fn test_subarray_sum() {
    println!("{}", subarray_sum2(vec![1, 2, 3], 3));
}


/// https://leetcode.cn/problems/sliding-window-maximum/description/?envType=study-plan-v2&envId=top-100-liked
/// 239. 滑动窗口最大值
/// 给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。
/// 你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
//
// 返回 滑动窗口中的最大值
// TIP: [3]
pub fn max_sliding_window(nums: Vec<i32>, k: i32) -> Vec<i32> {
    let mut ans = vec![];
    // 先维护一个双端队列
    let mut deque = std::collections::vec_deque::VecDeque::new();
    for (i, &v) in nums.iter().enumerate() {
        //首先把超出窗口期的数据丢掉
        while let Some(&h) = deque.front() {
            if h + (k as usize) < i + 1 {
                deque.pop_front();
            } else { break; }
        }
        // while !deque.is_empty() && *deque.front().unwrap() + (k as usize) < i + 1 {
        //     deque.pop_front();
        // }
        //维护一个单向递减队列
        while let Some(&h) = deque.back() {
            if nums[h] < v {
                deque.pop_back();
            } else { break; }
        }
        // while !deque.is_empty() && nums[*deque.back().unwrap()] < v {
        //     deque.pop_back();
        // }
        //加入当前元素
        deque.push_back(i);
        //取出首元素
        if i + 1 >= k as usize {
            ans.push(nums[*deque.front().unwrap()]);
        }
    }

    ans
}

#[test]
pub fn test_max_sliding_window() {
    println!("{:?}", max_sliding_window(vec![1, 3, -1, -3, 5, 3, 6, 7], 3));
}

/// https://leetcode.cn/problems/minimum-window-substring/description/?envType=study-plan-v2&envId=top-100-liked
/// 76. 最小覆盖子串
/// 给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。
/// 如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
///
/// TIP: 面对子串问题，考虑滑动窗口和队列处理，对于复杂的字符串比较考虑优先做值转换
pub fn min_window(s: String, t: String) -> String {
    let sp = s.to_lowercase().chars().collect::<Vec<char>>();
    let st = t.to_lowercase();
    let mut pattern = vec![0; 26];
    for x in st.chars() {
        pattern[x as usize - 'a' as usize] += 1;
    }

    let check_override = |matcher: &Vec<i32>| -> bool {
        for i in 0..26 {
            if matcher[i] < pattern[i] { return false; }
        }
        true
    };
    let mut l = 0;
    let mut r = 0;
    let mut len = usize::MAX;
    let mut ans = "";

    let mut matcher = vec![0; 26];

    while r < sp.len() {
        matcher[sp[r] as usize - 'a' as usize] += 1;
        while check_override(&matcher) {
            if len > r - l + 1 {
                len = r - l + 1;
                ans = &s[l..=r];
            }
            matcher[sp[l] as usize - 'a' as usize] -= 1;
            l += 1;
        }
        r += 1;
    }
    if len == usize::MAX { "".to_string() } else { ans.to_string() }
}

#[test]
pub fn test_min_window() {
    println!("{}", min_window("ab".to_string(), "A".to_string()));
}